package leetcode_BFS;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/6/25 21:34
 * 单词接龙
 * 算法：BFS
 * 求 beginWord 到 endWord 的最小路径，可以看成一个图
 * 求图上两点之间的最短
 */
public class _127 {

    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        HashSet<String> wordSet = new HashSet<>(wordList);
        if (wordSet.isEmpty() || !wordSet.contains(endWord)) return 0;
        wordSet.remove(beginWord);
        HashSet<String> visited = new LinkedHashSet<>();
        visited.add(beginWord);
        Queue<String> queue = new LinkedList<>();
        queue.offer(beginWord);
        int step = 1;
        while (!queue.isEmpty()) {
            int curSize = queue.size();
            for (int i = 0; i < curSize; i++) {
                String currentWord = queue.poll();
                if (bfs(currentWord, endWord, wordSet, visited, queue)) return step + 1;
            }
            ++step;
        }
        return 0;
    }
    boolean bfs(String curWord, String endWord, HashSet<String> wordSet, HashSet<String> visited, Queue<String> queue) {
        char[] array = curWord.toCharArray();
        for (int i = 0; i < array.length; i++) {
            char originChar = array[i];
            for (char c = 'a'; c <= 'z'; c++) {
                array[i] = c;
                String s = new String(array);
                if (wordSet.contains(s)) {
                    if (endWord.equals(s)) return true;
                    if (!visited.contains(s)) {
                        queue.offer(s);
                        visited.add(s);
                    }
                }
            }
            array[i] = originChar;
        }
        return false;
    }


}
